package alogrithm.solution;

import java.util.ArrayList;

/*
 * 第21题
2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
 */
public class P21 {
	public static ArrayList<ArrayList<Integer>> getAllComposition(int n,int m)
	{
		if(m==0)
		{
			ArrayList<ArrayList<Integer>> result=new ArrayList<>();
			result.add(new ArrayList<Integer>());
			return result;
		}
		else if(m>0)
		{
			if(n==0)return null;
			ArrayList<ArrayList<Integer>> list=new ArrayList<>();
			ArrayList<ArrayList<Integer>> tmp1=getAllComposition(n-1, m-n);
			if(tmp1!=null)
			{
				for(ArrayList<Integer> l:tmp1)
					l.add(n);
				list.addAll(tmp1);
			}
			ArrayList<ArrayList<Integer>> tmp2=getAllComposition(n-1, m);
			if(tmp2!=null)
			{
				list.addAll(tmp2);
			}
			return list;
		}
		return null;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<ArrayList<Integer>> result=getAllComposition(5, 7);
		for(ArrayList<Integer> l:result)
			System.out.println(l);

	}

}
